import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 03010570
 * @date 2020/07/09
 * describe:    LeetCode : 78、子集    https://leetcode-cn.com/problems/subsets/
 */
public class LeetCode_78 {
    static int count=0;
    public static void main(String[] args) {
        LeetCode_78 code78 = new LeetCode_78();
        List<List<Integer>> subsets = code78.subsets2(new int[]{1, 2, 3});
        for (List<Integer> subset : subsets) {
            for (Integer integer : subset) {
                System.out.print( integer +" ,");
            }
            System.out.println();
        }
        System.out.println(subsets.size());
        System.out.println(count);
    }

    /**
     *  迭代
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets2(int[] nums) {
        LinkedList<List<Integer>> result = new LinkedList<>();
//        result.add(new LinkedList<Integer>());
        dfs(0,nums,new LinkedList<>(),result);
        return result;
    }

    private void dfs(int index, int[] nums, LinkedList<Integer> temp, LinkedList<List<Integer>> result) {
        if(index == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }
        dfs(index+1,nums,temp,result);
        temp.add(nums[index]);
        dfs(index+1,nums,temp,result);
        temp.removeLast();
    }


    /**
         *  回溯
         * @param nums
         * @return
         */
    public List<List<Integer>> subsets(int[] nums) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        result.add(new LinkedList<Integer>());
        backtrack(0,nums,new LinkedList<>(),result);
        return result;
    }

    private void backtrack(int start, int[] nums, LinkedList<Integer> temp, LinkedList<List<Integer>> result) {
        for(int i=start; i < nums.length;i++){
            count++;
            temp.add(nums[i]);
            result.add(new ArrayList<>(temp));
            backtrack(i+1,nums,temp,result);
            temp.removeLast();
        }
    }

}
